1. Technical Field
The present invention relates to an IP address lookup method and an IP address lookup apparatus using a Bloom filter and a multi-hashing architecture. More particularly, the present invention relates to an IP address lookup method and an IP address lookup apparatus that perform IP address lookup by using a single Bloom filter and a single multi-hash table without implementing a Bloom filter and a hash table for each prefix length.
2. Related Art
Currently, more efficient IP address lookup is required to forward a packet inputted into a router with a line speed. The function of the IP address lookup is to determine an output port of the packet by searching an entry that matches the prefix, which is a network part of a destination address of the inputted packet. Among the matching entries of a table, which are stored in the router, the longest matching prefix becomes the best matching prefix (BMP).
In the IP address lookup, the most important element is the number of times in which a memory is accessed, which is required to determine the BMP. A second important element is a size of the memory for storing a routing table. Further, how easy it is to update a table, which can easily add or remove the prefix, is also an important element and in addition, extensibility to IPv6 from IPv4 is also required.
A known IP address lookup architecture includes an algorithm based on a tree architecture such as binary trie (B-Trie), binary search tree (BST), binary search on range (BSR), etc., an algorithm based on a hashing architecture such as parallel hashing, multiple hashing, parallel-multiple hashing in which the parallel hashing and the multiple hashing are mixed, etc., and an algorithm based on the Bloom filter, etc.
FIG. 1 is a diagram illustrating an IP address lookup architecture using a known parallel hashing architecture.
This architecture uses a cyclic redundancy check generator as a hashing function. First, a plurality of hashing indexes are extracted by inputting prefixes into the CRC generator (two hashing indexes are extracted in FIG. 1) and the prefixes are stored using a multi-hashing method. If the prefixes cannot be stored in a given bucket due to collision, the prefixes are stored in an overflow table.
The prefixes are stored in the hash table for each length thereof. Thereafter, when a predetermined IP address is inputted, the prefixes of the IP address are sequentially inputted into the CRC generator from most significant bit (MSB), such that two hashing indexes are generated for each prefix length. That is, when 8 bits are first inputted, two hashing indexes are generated therefrom and when 1 bit is additionally inputted, two hashing indexes corresponding to 9 bits are generated. According to this sequence, two hashing indexes are generated for each prefix length from 8 bits to 32 bits.
Since the parallel-multiple hashing architecture performs the IP address lookup for each prefix length, the hash table is also implemented in a separate SRAM for each prefix length. Therefore, a matched prefix is searched by accessing each hash table in parallel using the hashing indexes generated for each prefix length. The search result is outputted to a priority encoder. The priority encoder outputs a result of the longest prefix that matches the inputted address among outputted results as the BMP.
Since the parallel hashing architecture performs the IP address lookup in parallel for each prefix length, the parallel hashing architecture has an advantage in that the search speed is fast. However, since the parallel hashing architecture must configure the hash table for each prefix length, the hashing architecture is complex to implement and an additional memory is required for each prefix length, resulting in that the parallel hashing architecture consumes excessive amounts of memories.
FIG. 2 is a diagram illustrating an IP address lookup architecture using a known Bloom filter.
This architecture includes a Bloom filter for each prefix length to query the inputted prefixes to the Bloom filter in parallel for each length and it is checked whether a matched prefix is provided in the hash table by accessing the hash table from the longest prefix for only a length determined to belong to the hash table by the Bloom filter.
Since the architecture using the Bloom filter tries to access the hash table only with respect to a length passing the Bloom filter, the architecture has an advantage of reducing the number of times in which the memory is accessed.
However, since the IP address lookup architecture using the Bloom filter also searches the IP address for each prefix length, the IP address lookup architecture must configure the Bloom filter for each prefix length, such that the IP address lookup architecture is difficult to implement. Further, this architecture assumes that the hash table is configured for each prefix length and proposes that a controlled prefix expansion (CPE) scheme is used in order to reduce the number of hash tables. In the case of using the CPE scheme, prefix replication is inevitable.
As described above, since the known IP address lookup architecture configures the hash table for each prefix length and/or includes the Bloom filter for each prefix length in order to increase the search speed, the IP address lookup architecture is difficult to implement and the number of memories increase, thereby increasing manufacturing cost.
The present invention is contrived to solve the above-mentioned problems. An object of the present invention is to provide an IP address lookup apparatus and an IP address lookup method that can search an IP address by using a single Bloom filter and a single multi-hash table without implementing a Bloom filter and a hash table for each prefix length.
According to a first aspect of the present invention, an IP address lookup apparatus using a Bloom filter and a multi-hashing architecture includes a buffering means that outputs a prefix of an inputted address having the number of bits reduced by one bit whenever a control signal is received at the time of outputting the prefix of the inputted address; a hashing hardware that generates a plurality of hashing indexes by hashing the prefix (hereinafter, referred to as “output prefix”) outputted from the buffering means; a Bloom filter that determines whether or not the output prefix is an entry of the hash table by using the plurality of hashing indexes; and a processor that includes the hash table and an overflow table and outputs a prefix that matches the output prefix by searching entries of locations of the hash table indicated by the plurality of hashing indexes and entries stored in the overflow table when a Bloom filter's determination result is positive and outputs the control signal to the buffering means when the matched prefix is not provided or the Bloom filter's determination result is negative.
According to a second aspect of the present invention, an IP address lookup apparatus using a Bloom filter and a multi-hashing architecture includes a buffering means that outputs a prefix of an inputted address having the number of bits reduced by one bit whenever a control signal is received at the time of outputting the prefix of the inputted address; a hashing hardware that generates a plurality of first hashing indexes and a plurality of second hashing indexes by hashing the prefix (hereinafter, referred to as “output prefix”) outputted from the buffering means; a Bloom filter that determines whether or not the output prefix is an entry of the hash table by using the plurality of first hashing indexes; and a processor that includes the hash table and an overflow table and outputs a prefix that matches the output prefix by searching entries of locations of the hash table indicated by the plurality of second hashing indexes and entries stored in the overflow table when a Bloom filter's determination result is positive and outputs the control signal to the buffering means when the matched prefix is not provided or the Bloom filter's determination result is negative.
According to a third aspect of the present invention, an IP address lookup method using a Bloom filter and a multi-hashing architecture includes (a) generating a plurality of hashing indexes by hashing inputted prefixes; (b) determining whether a bit vector corresponding to the plurality of hashing indexes is positive or negative by using the Bloom filter; (c) outputting a prefix that matches the inputted prefix by searching entries of locations indicated by the plurality of hashing indexes in the hash table when the bit vector is determined to be positive in step (b); (d) outputting the prefix that matches the inputted prefix by searching entries stored in the overflow table; (e) outputting as a result value a matched prefix having the longest length among the prefix outputted in step (c) and the prefix outputted in step (d), which matches the prefix; and (f) reinputting a prefix having the number of bits reduced from the inputted prefix by one bit and returning to step (a) when the bit vector is determined to be negative in step (b) or an entry matching the prefix is not provided in steps (c) and (d).
According to a fourth aspect of the present invention, an IP address lookup method using a Bloom filter and a multi-hashing architecture includes (a) generating a plurality of first hashing indexes and a plurality of second hashing indexes by hashing inputted prefixes; (b) determining whether a bit vector corresponding to the plurality of first hashing indexes is positive or negative by using the Bloom filter; (c) outputting a prefix that matches the inputted prefix by searching entries of locations indicated by the plurality of second hashing indexes in the hash table when the bit vector is determined to be positive in step (b); (d) outputting the prefix that matches the inputted prefix by searching entries stored in the overflow table; (e) outputting as a result value a matched prefix having the longest length among the prefix outputted in step (c) and the prefix outputted in step (d), which matches the prefix; and (f) reinputting a prefix having the number of bits reduced from the inputted prefix by one bit and returning to step (a) when the bit vector is determined to be negative in step (b) or an entry matching the prefix is not provided in steps (c) and (d).